fn print_board(board: &[[u8; 9]; 9]) {
    for row in 0..9 {
        for col in 0..9 {
            let val = board[row][col];
            if val == 0 {
                print!(". ");
            } else {
                print!("{} ", val);
            }
        }
        println!();
    }
}

fn is_valid(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool {
    // Check row
    for c in 0..9 {
        if board[row][c] == num {
            return false;
        }
    }
    // Check column
    for r in 0..9 {
        if board[r][col] == num {
            return false;
        }
    }
    // Check 3x3 box
    let box_row_start = (row / 3) * 3;
    let box_col_start = (col / 3) * 3;
    for r in box_row_start..(box_row_start + 3) {
        for c in box_col_start..(box_col_start + 3) {
            if board[r][c] == num {
                return false;
            }
        }
    }
    true
}

fn find_empty_cell(board: &[[u8; 9]; 9]) -> Option<(usize, usize)> {
    for r in 0..9 {
        for c in 0..9 {
            if board[r][c] == 0 {
                return Some((r, c));
            }
        }
    }
    None
}

fn solve_sudoku(board: &mut [[u8; 9]; 9]) -> bool {
    let empty = find_empty_cell(board);
    if empty.is_none() {
        return true; // Solved
    }
    let (row, col) = empty.unwrap();

    for num in 1..=9 {
        if is_valid(board, row, col, num) {
            board[row][col] = num;
            if solve_sudoku(board) {
                return true;
            }
            board[row][col] = 0; // backtrack
        }
    }
    false
}

fn main() {
    let mut test_boards = vec![
        // Example 1
        [
            [5,3,0,0,7,0,0,0,0],
            [6,0,0,1,9,5,0,0,0],
            [0,9,8,0,0,0,0,6,0],
            [8,0,0,0,6,0,0,0,3],
            [4,0,0,8,0,3,0,0,1],
            [7,0,0,0,2,0,0,0,6],
            [0,6,0,0,0,0,2,8,0],
            [0,0,0,4,1,9,0,0,5],
            [0,0,0,0,8,0,0,7,9],
        ],
        // Example 2
        [
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,3,0,8,5],
            [0,0,1,0,2,0,0,0,0],
            [0,0,0,0,0,0,0,0,7],
            [0,0,0,0,1,0,0,0,0],
            [3,0,0,0,0,0,0,0,0],
            [0,0,0,0,4,0,1,0,0],
            [5,7,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
        ],
        // Example 3
        [
            [1,0,0,0,0,7,0,9,0],
            [0,3,0,0,2,0,0,0,8],
            [0,0,9,6,0,0,5,0,0],
            [0,0,5,3,0,0,9,0,0],
            [0,1,0,0,0,0,0,0,2],
            [0,0,6,0,0,3,0,0,0],
            [0,6,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
        ],
        // Example 4
        [
            [0,0,0,2,6,0,7,0,1],
            [6,8,0,0,7,0,0,9,0],
            [1,9,0,0,0,4,5,0,0],
            [8,2,0,1,0,0,0,4,0],
            [0,0,4,6,0,2,9,0,0],
            [0,5,0,0,0,3,0,2,8],
            [0,0,9,3,0,0,0,7,4],
            [0,4,0,0,5,0,0,3,6],
            [7,0,3,0,1,8,0,0,0],
        ],
        // Example 5
        [
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,3,0,8,5],
            [0,0,1,0,2,0,0,0,0],
            [0,0,0,0,0,0,0,0,7],
            [0,0,0,0,1,0,0,0,0],
            [3,0,0,0,0,0,0,0,0],
            [0,0,0,0,4,0,1,0,0],
            [5,7,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
        ],
        // Example 6 (a harder one)
        [
            [0,0,0,0,0,0,0,0,6],
            [0,0,0,0,0,3,0,0,0],
            [0,0,1,0,2,0,0,0,0],
            [0,0,0,0,6,0,0,0,3],
            [4,0,0,8,0,3,0,0,1],
            [7,0,0,0,2,0,0,0,6],
            [0,6,0,0,0,0,2,8,0],
            [0,0,0,4,1,9,0,0,5],
            [0,0,0,0,8,0,0,7,9],
        ],
        // Example 7
        [
            [9,0,0,0,0,0,0,0,5],
            [0,1,0,0,0,5,0,0,0],
            [0,0,0,3,0,0,0,8,0],
            [0,0,0,0,0,6,0,0,0],
            [0,0,0,0,0,0,2,0,0],
            [3,0,7,0,0,0,0,0,1],
            [0,6,0,0,0,0,0,9,0],
            [0,0,0,4,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
        ],
        // Example 8
        [
            [2,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,3,0,8,5],
            [0,0,1,0,2,0,0,0,0],
            [0,0,0,0,0,0,0,0,7],
            [0,0,0,0,1,0,0,0,0],
            [3,0,0,0,0,0,0,0,0],
            [0,0,0,0,4,0,1,0,0],
            [5,7,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
        ],
        // Example 9
        [
            [0,0,0,0,7,0,0,0,0],
            [6,0,0,1,9,5,0,0,0],
            [0,9,8,0,0,0,0,6,0],
            [8,0,0,0,6,0,0,0,3],
            [4,0,0,8,0,3,0,0,1],
            [7,0,0,0,2,0,0,0,6],
            [0,6,0,0,0,0,2,8,0],
            [0,0,0,4,1,9,0,0,5],
            [0,0,0,0,8,0,0,7,0],
        ],
        // Example 10
        [
            [0,0,0,4,0,0,0,0,0],
            [0,0,0,0,0,3,0,8,5],
            [0,2,1,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,7],
            [0,0,0,0,1,0,0,0,0],
            [3,0,0,0,0,0,0,0,0],
            [0,0,0,0,4,0,1,0,0],
            [5,7,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
        ],
    ];

    for (i, board) in test_boards.iter_mut().enumerate() {
        println!("Test Sudoku #{} (Before):", i+1);
        print_board(board);
        if solve_sudoku(board) {
            println!("Solved Sudoku #{}:", i+1);
            print_board(board);
        } else {
            println!("No solution found for Sudoku #{}.", i+1);
        }
        println!("-----------------------------------------");
    }
}
